package org.xqh.study.leetcode.bytedance;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName ReceiveRainWater
 * @Description 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 * @Author xuqianghui
 * @Date 2021/2/8 15:09
 * @Version 1.0
 */
public class ReceiveRainWater {

    /**
     * 本题暴力解法 :
     * 1. 求出每一个柱子 能 接多少雨水.
     * 2. 需要遍历 每一个 柱子 的 左右两边的 最大高度.
     * 时间复杂度 O(n2)
     * @param args
     */

    public static void main(String[] args) {
        int[] height = {0, 1, 5, 3, 0, 2, 4, 5};
//        int[] height = {1, 2, 5, 3, 6, 1};
        System.out.println(trap22(height));;
    }




    public static int trap11(int[] height) {
        int len = height.length;
        if(len < 2){
            return 0;
        }

        /**
         * 如果下一个元素 大于等于 滚动变量 最大高度
         */
        Deque<Integer> deque = new ArrayDeque<>(len);
        int water = 0;
        for(int i = 0; i < len; i ++){
            int h = height[i];
            while (!deque.isEmpty() && height[deque.peekLast()] <= h){
                int pollIdx = deque.pollLast();//弹出
                Integer curLast = deque.peekLast();//当前 栈末 元素
                if(curLast == null){
                    break;
                }
                int minH = Math.min(height[curLast], h);
                water += (i - curLast - 1) * (minH - height[pollIdx]);
            }
            deque.offer(i);
        }
        return water;
    }


    /**
     * 动态规划
     * @param heights
     * @return
     */
    public static int trap22(int[] heights) {
        int len = heights.length;
        if(len < 2){
            return 0;
        }

        /**
         * 每个元素 从左边看 能看到的 最大的 柱形高度
         */
        int[] left = new int[len];
        left[0] = heights[0];
        int[] right = new int[len];//从右边看 能看到 最大柱形高度
        right[len - 1] = heights[len - 1];
        int lMax = left[0];
        for(int i = 1; i < len; i ++){
            lMax = Math.max(lMax, heights[i]);
            left[i] = lMax;
        }
        int rMax = right[len - 1];
        for(int i = len - 2; i >= 0; i--){
            rMax = Math.max(rMax, heights[i]);
            right[i] = rMax;
        }

        int ans = 0;
        for(int i = 0; i < len; i++){
            ans += Math.min(left[i], right[i]) - heights[i];
        }

        return ans;
    }
}
